package com.leetcode.p0;

import com.utils.DataUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test51 {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queue = new int[n];
        Arrays.fill(queue, -1);
        Set<Integer> column = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();

        dfs(result, queue, column, diagonals1, diagonals2, 0, n);

        return result;
    }

    private void dfs(List<List<String>> result,
                     int[] queue,
                     Set<Integer> column,
                     Set<Integer> diagonals1,
                     Set<Integer> diagonals2,
                     int row,
                     int n) {
        if (row == n) {
            result.add(generateBoard(queue, n));
        } else {
            for (int i = 0; i < n; i++) {
                if (column.contains(i)) {
                    continue;
                }

                int diagonals1_1 = row - i;
                if (diagonals1.contains(diagonals1_1)) {
                    continue;
                }

                int diagonals2_2 = row + i;
                if (diagonals2.contains(diagonals2_2)) {
                    continue;
                }

                queue[row] = i;
                column.add(i);
                diagonals1.add(diagonals1_1);
                diagonals2.add(diagonals2_2);

                dfs(result, queue, column, diagonals1, diagonals2, row + 1, n);

                queue[row] = -1;
                column.remove(i);
                diagonals1.remove(diagonals1_1);
                diagonals2.remove(diagonals2_2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    public static void main(String[] args) {
        Test51 test = new Test51();
        List<List<String>> result = test.solveNQueens(4);
//        System.out.println(result);
        DataUtils.printListListString(result);
    }

}
